/* Kruskal.java */

import java.util.Hashtable;
import graph.*;
import set.*;
import java.util.Arrays;

/**
 * The Kruskal class contains the method minSpanTree(), which implements
 * Kruskal's algorithm for computing a minimum spanning tree of a graph.
 */

public class Kruskal {

  /**
   * minSpanTree() returns a WUGraph that represents the minimum spanning tree
   * of the WUGraph g.  The original WUGraph g is NOT changed.
   */
  public static WUGraph minSpanTree(WUGraph g) {
    Edge[] earray = new Edge[g.edgeCount()];
    Hashtable<VertexPair, Integer> ehash = new Hashtable<VertexPair, Integer>();
    Integer dummy = new Integer(0);
    int index = 0;
    filler:
    for (Object v:  g.getVertices()) {
    	Neighbors n = g.getNeighbors(v);
    	if (n != null) {
    		for (int i = 0; i < n.neighborList.length; ++i) {
    			Edge temp = new Edge(v, n.neighborList[i], n.weightList[i]);
    			if (!ehash.containsKey(temp.getVertex())) {
    				ehash.put(temp.getVertex(), dummy);
    				earray[index] = temp;
    				++index;
    				if (index == earray.length) {
    					break filler;
    				}
    			}
    		}
    	}
    }
    Arrays.sort(earray);
    System.out.println(Arrays.deepToString(earray));
    
    WUGraph t = new WUGraph();
    VertexSet vSet = new VertexSet(g.getVertices());
    for (Object v : g.getVertices()) {
    	t.addVertex(v);
    }
    for (Edge e : earray) {
    	if (vSet.find(e.getVertex().getU()) != vSet.find(e.getVertex().getV()) ) {
    		System.out.println(e.weight());
    		System.out.println(vSet.find(e.getVertex().getU()) + " " + vSet.find(e.getVertex().getV()));
    		t.addEdge(e.getVertex().getU(), e.getVertex().getV(), e.weight());
    		vSet.union(e.getVertex().getU(), e.getVertex().getV());
    	}
    }
    
    return t;
  }
}
